#include <iostream>

using namespace std;
#ifndef MAXV
#define MAXV 100
#define INF 0x3f3f3f3f
#endif

struct ArcNode{
    int adjvex;
    int weight;
    ArcNode * nextarc;
};
struct HNode{
    string info;
    ArcNode * firstarc;
};

class AdjGraph{
public:
    HNode adjlist[MAXV];
    int n,e;
    AdjGraph()
    {
        for(int i= 0;i<MAXV;i++)
        {
            adjlist[i].firstarc = NULL;
        }
    }
    ~AdjGraph()
    {
        ArcNode * pre,*p;
        for(int i=0;i<n;i++)
        {
            pre = adjlist[i].firstarc;
            if(pre != NULL)
            {
                p = pre ->nextarc;
                while(p != NULL)
                {
                    delete pre;
                    pre = p;
                    p = p->nextarc;
                }
                delete pre;
            }
        }
    }
    /*通过边数组a、顶点数n和边数e来建立痛的邻接表*/
    void CreateAdjGraph(int a[][MAXV],int n,int e)
    {
        ArcNode * p;
        this -> n =n; this -> e = e;
        for(int i = 0;i<n;i++)
        {
            for(int j= n-1;j>=0;j--)
            {
                if(a[i][j] !=0 && a[i][j]!=INF)
                {
                    p = new ArcNode();
                    p->adjvex = j;
                    p->weight = a[i][j];
                    p->nextarc = adjlist[i].firstarc;
                    adjlist[i].firstarc = p;
                }
            }
        }
    }
    void DispAdjGraph()
    {
        ArcNode * p;
        for(int i=0;i<n;i++)
        {
            printf(" [%d]",i);
            p = adjlist[i].firstarc;
            if(p != NULL) printf("→");
            while (p != NULL)
            {
                printf("(%d,%d)",p->adjvex,p->weight);
                p = p->nextarc;
            }
            printf("\n");
        }
    }
};

int main()
{
    AdjGraph G;
    int n=5,e=5;
    int A[MAXV][MAXV] = 
    {{0,8,INF,5,INF},
    {INF,0,3,INF,INF},
    {INF,INF,0,INF,6},
    {INF,INF,9,0,INF},
    {INF,INF,INF,INF,0}};
    
    G.CreateAdjGraph(A,n,e);

    cout<< "图的邻接表：\n"; G.DispAdjGraph();
    cout<<"销毁图\n";
    return 0;
}